#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int>len(n, 1), cnt(n, 1);
        int retlen = 1, retcnt = 1;
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (nums[j] < nums[i])
                {
                    if (len[j] + 1 == len[i]) cnt[i] += cnt[j];
                    else if (len[j] + 1 > len[i])
                    {
                        len[i] = len[j] + 1, cnt[i] = cnt[j];
                    }
                }
            }
            if (retlen == len[i])
                retcnt += cnt[i];
            else if (retlen < len[i])
            {
                retlen = len[i];
                retcnt = cnt[i];
            }
        }
        return retcnt;
    }
};